package com.openess.bigsearch.engine.utils.sort;

import java.util.Comparator;

/**
 * 折半插入排序，属于直接插入排序的改进版，在查找插入点的时候，弃用顺序查找，改用折半查找
 * 
 * @author TuTu
 * 
 */
public class BinaryInsertionSort<E> implements Sort<E> {
	/**
	 * 折半插入排序
	 * 
	 * @param array
	 * @param p
	 * @param r
	 */
	public void sort(E[] array, int p, int r, Comparator<? super E> c) {
		for (int j = p + 1; j <= r; j++) {
			E key = array[j];
			int low = p;
			int high = j - 1;
			// 拿到待插入位置
			int index = search(array, key, low, high, c);
			// 进行移位
			for (int i = j - 1; i >= index; i--) {
				array[i + 1] = array[i];
			}
			// 插入值
			array[index] = key;
		}
	}

	/**
	 * 利用折半查找插入点
	 * 
	 * @param array
	 *            待查找数组
	 * @param key
	 *            需要查找插入位置的关键字
	 * @param start
	 *            查找的起始位置
	 * @param end
	 *            查找的终止位置(包括)
	 * @return 插入点
	 */
	private int search(E[] array, E key, int start, int end,
			Comparator<? super E> c) {
		int mid;
		int low = start;
		int high = end;
		while (low <= high) {
			mid = (low + high) / 2;
			// >=0为了保证排序的稳定
			if (c.compare(key, array[mid]) >= 0) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}
		return low;
	}
}
